package link;

import array.ListNode;

public class InsertionSortList147 {
    public ListNode insertionSortList(ListNode head) {
        ListNode idle = new ListNode(Integer.MIN_VALUE);
        idle.next = head;
        ListNode index = head;
        while (index != null && index.next != null) {
            if (index.val > index.next.val) {
                ListNode temp = idle;
                while (temp.next.val < index.next.val) {
                    temp = temp.next;
                }
                ListNode tt = temp.next;
                temp.next = index.next;
                index.next=index.next.next;
                temp.next.next = tt;
            } else {
                index = index.next;
            }

        }
        return idle.next;
    }
}
